package org.example.myleet.p1417;

public class Solution {
    public String reformat(String s) {
        int alphabetCount = 0, digitCount = 0;
        int[] alphabets = new int[26];
        int[] digits = new int[10];
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                ++digitCount;
                ++digits[c - '0'];
            } else {
                ++alphabetCount;
                ++alphabets[c - 'a'];
            }
        }
        if (Math.abs(digitCount - alphabetCount) > 1) {
            return "";
        }
        StringBuilder res = new StringBuilder();
        boolean chooseAlphabet = alphabetCount >= digitCount;
        int a = 0, d = 0;
        while (a < 26 || d < 10) {
            if (chooseAlphabet) {
                while (a < 26 && alphabets[a] == 0) {
                    ++a;
                }
                chooseAlphabet = false;
                if (a >= 26) {
                    continue;
                }
                --alphabets[a];
                res.append((char)(a + 'a'));
            } else {
                while (d < 10 && digits[d] == 0) {
                    ++d;
                }
                chooseAlphabet = true;
                if (d >= 10) {
                    continue;
                }
                --digits[d];
                res.append((char)(d + '0'));
            }
        }
        return res.toString();
    }
}
